﻿#include <iostream>
#include <unordered_map>

using namespace std;

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

static int noRepeatedSubString(const char* text)
{
    auto strSize = strlen(text);
    int* arr = (int*)malloc(strSize * sizeof(int));
    memset(arr, 0, strSize * sizeof(int));

    int max = 0;
    unordered_map<char, int> positionMap;
    for (int i = 0; i < strSize; i++)
    {
        auto c = text[i];
        if (i == 0)
        {
            arr[i] = 1;
        }
        else
        {
            arr[i] = arr[i - 1] + 1;
            auto existsPair = positionMap.find(c);
            if (existsPair != positionMap.end())
            {
                auto lastPosition = existsPair->second;
                arr[i] = MIN((i - lastPosition), arr[i]);
            }
        }

        max = MAX(max, arr[i]);
        positionMap[c] = i;
    }

    return max;
}

//  在一个字符串中找到没有重复字符子串中最长的长度。
//  例如:
// abcabcbb没有重复字符串的最长子串是abc，长度是3
//  bbbbb, 答案是b，长度是1
//  pwwkew，答案是wke，长度是3
//  要求：
//  答案必须是子串，"pwke"是有个子字符序列，但不是一个子字符串。
// 
// 思路:
// 求解以每一个位置作为结尾，没有重复的最长子串，最终求最大值。
//  设字符串数组是characters, 存放每一个位置的无重复最长子串长度的数组是A,
//  characters : ...  e   a   b   c    d ? ...
//    indexes : ... i - 5 i - 4 i - 3 i - 2  i - 1  i ...    i
// 
// 有两种可能性,
//  1. 假设A[i - 1] = m, 则A[i]有可能是m + 1
//  2. 查看i位置之前，是否有和characters[i]一样的字符，假设找到了，位置是j，即characters[i] == // characters[j]
//  则A[i]有可能是i - j
// 
// 两种可能性取最小的哪一个。
int main_LongestNoRepeatedSubString()
{
    char text[256] = "abcdefabcd";
    int max = noRepeatedSubString(text);
    printf("%d\n", max);
    return 0;
}